package q857_mincostToHireWorkers;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    /*
    此题的核心思想在于：
    对于每个员工都有一个性价比：wage / quality
    那么发工资时，期望每一个员工在quality高的同时 wage低
    但是每个员工的工资不能低于它的wage值，所以对于团队组来说
    1 性价比从高到低排列，优先使用性价比高的，但是价钱由性价比低的那个人决定
    2 你出的钱永远 大于等于 每个人的最低心里预期
    3 大顶堆里维护k个人，我只要人数，不要求质量，所以把干活儿多的人踢出去，这样省钱
    4 维护大顶堆、小顶堆 topK的和，也可以按照这个题的方式去做，搞一个sum，sum += 入栈的元素，sum -= pop出去的元素 这样剩下的就是topK的和了
     */
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Integer[] h = new Integer[n];
        for (int i = 0; i < n; i++) {
            h[i] = i;
        }
        Arrays.sort(h, (a, b) -> {
            return quality[b] * wage[a] - quality[a] * wage[b];
        });
        double res = 1e9;
        double totalq = 0.0;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int i = 0; i < k - 1; i++) {
            totalq += quality[h[i]];
            pq.offer(quality[h[i]]);
        }
        for (int i = k - 1; i < n; i++) {
            int idx = h[i];
            totalq += quality[idx];
            pq.offer(quality[idx]);
            double totalc = ((double) wage[idx] / quality[idx]) * totalq;
            res = Math.min(res, totalc);
            totalq -= pq.poll();
        }
        return res;
    }
}
